package cn.edu.jxau.test;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;

/**
 * @author 付大石
 */
public class Sort {

    public static void main(String[] args) throws IOException {

//        int len = 10000;
//        int[] arr = new int[len];
//        DataInputStream in = new DataInputStream(new FileInputStream("C:\\Users\\PC-Clive\\Desktop\\data.dat"));
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = in.readInt();
//        }
//        in.close();

        int[] arr = { 1, 4, 3, 4, 2, 4, 4 };
        System.out.println(Arrays.toString(arr));
        long start = System.nanoTime();
        sort(arr);
        long end = System.nanoTime();
        System.out.println(Arrays.toString(arr));
        System.out.println("spend tiem:" + (end - start));

    }

    /**
     * 快速排序：每次切分过后，切分元素的左半部没有比它的的元素存在，切分元素的右半部没有比它小的元素存在
     * 
     * 1.一不小心可能会造成平方级的排序效率
     * 2.处理切分元素值有重复的情况
     * @param arr
     */
    private static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int low, int high) {

        if (high <= low) {
            return;
        }
        int p = partition(arr, low, high);
        System.out.printf("partition:%d,%s\n", p, Arrays.toString(arr));
        sort(arr, low, p - 1);
        sort(arr, p + 1, high);
    }

    private static int partition(int[] arr, int low, int high) {

        int i = low;
        int j = high + 1;
        int p = arr[low]; // 切分元素
        while (true) {
            while (arr[++i] < p) {
                if (i == high) {
                    break;
                }
            }
            while (arr[--j] > p)
                ;
            ;
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
        }
        swap(arr, low, j); // 将切分元素放入正确的位置
        return j;
    }

    private static void swap(int[] arr, int i, int j) {

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
	
	//-----------------------------
	// 第二种写法
	//-----------------------------
	/**
	 * 非原地切分，空间复杂度O(n),这样写的话相比于归并排序就没有优势
	 *
	 */
	private static void sort(int[] arr, int[] aux, int low, int high) {

        if (high <= low) {
            return;
        }
        int p = partition(arr, aux, low, high);
        sort(arr, aux, low, p - 1);
        sort(arr, aux, p + 1, high);
    }

    private static int partition(int[] arr, int[] aux, int low, int high) {

        int p = arr[low]; // 切分元素
        int l = low;
        int r = high;
        for (int i = low + 1; i <= high; i++) {
            if (arr[i] < p) {
                aux[l++] = arr[i];
            } else {
                aux[r--] = arr[i];
            }
        }
        System.out.printf("%d\t%d\n", l, r);
        aux[l] = p;
        for (int i = low; i <= high; i++) {
            arr[i] = aux[i];
        }
        return l;
    }
}
